package cn.demoncat.util.lang.entity.data;

import java.util.function.Consumer;

/**
 * 二叉树结点
 * 
 * @author 延晓磊
 *
 * @since 2020年7月18日
 */
public class BinaryTreeNode<T> implements Comparable<BinaryTreeNode<T>> {

	// 数据
	protected T data;
	// 权值
	protected int weight;
	// 左指针
	protected BinaryTreeNode<T> left;
	// 左指针类型：0左结点，1前驱
	protected int leftType;
	// 右指针
	protected BinaryTreeNode<T> right;
	// 右指针类型：0右结点，1后继
	protected int rightType;
	// 父结点
	protected BinaryTreeNode<T> parent;

	/**
	 * 构建
	 * 
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月18日
	 */
	public BinaryTreeNode() {
		super();
	}

	/**
	 * 构建
	 * 
	 * @param data
	 *            数据
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月18日
	 */
	public BinaryTreeNode(T data) {
		super();
		this.data = data;
	}

	/**
	 * 数据
	 * 
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月21日
	 */
	public T getData() {
		return data;
	}

	public BinaryTreeNode<T> setData(T data) {
		this.data = data;
		return this;
	}

	/**
	 * 权值
	 * 
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月21日
	 */
	public Integer getWeight() {
		return weight;
	}

	public BinaryTreeNode<T> setWeight(int weight) {
		this.weight = weight;
		return this;
	}

	/**
	 * 左指针
	 * 
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月21日
	 */
	public BinaryTreeNode<T> getLeft() {
		return left;
	}

	public BinaryTreeNode<T> setLeft(BinaryTreeNode<T> left) {
		this.left = left;
		return this;
	}

	/**
	 * 左指针类型：0左结点，1前驱
	 * 
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月21日
	 */
	public int getLeftType() {
		return leftType;
	}

	public BinaryTreeNode<T> setLeftType(int leftType) {
		this.leftType = leftType;
		return this;
	}

	/**
	 * 右指针
	 * 
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月21日
	 */
	public BinaryTreeNode<T> getRight() {
		return right;
	}

	public BinaryTreeNode<T> setRight(BinaryTreeNode<T> right) {
		this.right = right;
		return this;
	}

	/**
	 * 右指针类型：0右结点，1后继
	 * 
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月21日
	 */
	public int getRightType() {
		return rightType;
	}

	public BinaryTreeNode<T> setRightType(int rightType) {
		this.rightType = rightType;
		return this;
	}

	/**
	 * 父结点
	 * 
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月22日
	 */
	public BinaryTreeNode<T> getParent() {
		return parent;
	}

	public BinaryTreeNode<T> setParent(BinaryTreeNode<T> parent) {
		this.parent = parent;
		return this;
	}

	/**
	 * 前序遍历：结点 > 左子树 > 右子树
	 * 
	 * @param fn
	 *            消费(数据)
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月18日
	 */
	public void preOrder(Consumer<T> fn) {
		// 操作结点
		fn.accept(this.data);
		// 遍历左子树
		if (this.left != null) {
			this.left.preOrder(fn);
		}
		// 遍历右子树
		if (this.right != null) {
			this.right.preOrder(fn);
		}
	}

	/**
	 * 中序遍历：左子树 > 结点 > 右子树
	 * 
	 * @param fn
	 *            消费(数据)
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月18日
	 */
	public void inOrder(Consumer<T> fn) {
		// 遍历左子树
		if (this.left != null) {
			this.left.inOrder(fn);
		}
		// 操作结点
		fn.accept(this.data);
		// 遍历右子树
		if (this.right != null) {
			this.right.inOrder(fn);
		}
	}

	/**
	 * 后序遍历：左子树 > 右子树 > 结点
	 * 
	 * @param fn
	 *            消费(数据)
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月18日
	 */
	public void postOrder(Consumer<T> fn) {
		// 遍历左子树
		if (this.left != null) {
			this.left.postOrder(fn);
		}
		// 遍历右子树
		if (this.right != null) {
			this.right.postOrder(fn);
		}
		// 操作结点
		fn.accept(this.data);
	}

	/**
	 * 前序遍历：结点 > 左子树 > 右子树
	 * 
	 * @param fn
	 *            消费(结点)
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月18日
	 */
	public void preOrderNode(Consumer<BinaryTreeNode<T>> fn) {
		// 操作结点
		fn.accept(this);
		// 遍历左子树
		if (this.left != null) {
			this.left.preOrderNode(fn);
		}
		// 遍历右子树
		if (this.right != null) {
			this.right.preOrderNode(fn);
		}
	}

	/**
	 * 中序遍历：左子树 > 结点 > 右子树
	 * 
	 * @param fn
	 *            消费(结点)
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月18日
	 */
	public void inOrderNode(Consumer<BinaryTreeNode<T>> fn) {
		// 遍历左子树
		if (this.left != null) {
			this.left.inOrderNode(fn);
		}
		// 操作结点
		fn.accept(this);
		// 遍历右子树
		if (this.right != null) {
			this.right.inOrderNode(fn);
		}
	}

	/**
	 * 后序遍历：左子树 > 右子树 > 结点
	 * 
	 * @param fn
	 *            消费(结点)
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月18日
	 */
	public void postOrderNode(Consumer<BinaryTreeNode<T>> fn) {
		// 遍历左子树
		if (this.left != null) {
			this.left.postOrderNode(fn);
		}
		// 遍历右子树
		if (this.right != null) {
			this.right.postOrderNode(fn);
		}
		// 操作结点
		fn.accept(this);
	}

	/**
	 * 查找结点
	 * 
	 * @param data
	 *            数据
	 * 
	 * @return 第一个查找到的结点，未找到返回null
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月18日
	 */
	public BinaryTreeNode<T> search(T data) {
		// 比较结点
		if (data.equals(this.data)) {
			return this;
		}
		// 遍历左子树
		BinaryTreeNode<T> result = null;
		if (this.left != null) {
			result = this.left.search(data);
			if (result != null) {
				return result;
			}
		}
		// 遍历右子树
		if (this.right != null) {
			result = this.right.search(data);
		}
		return result;
	}

	/**
	 * 删除结点：叶子结点-删除结点，分枝结点-删除子树
	 * 
	 * @param data
	 *            目标数据（删除第一个匹配到的结点）
	 * 
	 * @return 是否删除
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月18日
	 */
	public boolean removes(T data) {
		// 判断左结点
		if (this.left != null && data.equals(this.left.data)) {
			// 如果当前结点是data匹配结点的父结点，重置left（删除左结点）
			this.left = null;
			return true;
		}
		// 判断右结点
		if (this.right != null && data.equals(this.right.data)) {
			// 如果当前结点是data匹配结点的父结点，重置right（删除右结点）
			this.right = null;
			return true;
		}
		// 遍历左子树
		if (this.left != null) {
			if (this.left.removes(data)) {
				// 已找到data匹配结点的父结点，并清除其left
				return true;
			}
		}
		// 遍历右子树
		if (this.right != null) {
			// 查找data匹配结点的父结点，并清除其right
			return this.right.removes(data);
		}
		return false;
	}

	/**
	 * 左旋转
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月23日
	 */
	public void leftRotate() {
		// 根结点 > 左结点（向左旋转）
		BinaryTreeNode<T> node = new BinaryTreeNode<>();
		node.data = data;
		node.left = left;
		node.right = right.left;
		left = node;
		// 右结点 > 根结点（提升）
		data = right.data;
		right = right.right;
	}

	/**
	 * 右旋转
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月23日
	 */
	public void rightRotate() {
		// 根结点 > 右结点（向右旋转）
		BinaryTreeNode<T> node = new BinaryTreeNode<>();
		node.data = data;
		node.right = right;
		node.left = left.right;
		right = node;
		// 左结点 > 根结点（提升）
		data = left.data;
		left = left.left;
	}

	/**
	 * 双旋转
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月23日
	 */
	public void rotate() {
		// 子树高度
		int lh = leftHeight();
		int rh = rightHeight();
		if (lh - rh > 1) {
			// 左斜树，右旋转
			if (left != null && left.rightHeight() - left.leftHeight() > 1) {
				// 子树反向旋转
				left.leftRotate();
			}
			rightRotate();
		} else if (rh - lh > 1) {
			// 右斜树，左旋转
			if (right != null && right.leftHeight() - right.rightHeight() > 1) {
				// 子树反向旋转
				right.rightRotate();
			}
			leftRotate();
		}
	}

	/**
	 * 树的高度（以当前结点为根结点的）
	 * 
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月23日
	 */
	public int height() {
		return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
	}

	/**
	 * 左子树的高度（以当前结点为根结点）
	 * 
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月23日
	 */
	public int leftHeight() {
		return left == null ? 0 : left.height();
	}

	/**
	 * 右子树的高度（以当前结点为根结点）
	 * 
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月23日
	 */
	public int rightHeight() {
		return right == null ? 0 : right.height();
	}

	/**
	 * 比较器（权重）
	 * 
	 * @param o
	 * @return
	 *
	 * @author 延晓磊
	 *
	 * @since 2020年7月21日
	 */
	@Override
	public int compareTo(BinaryTreeNode<T> o) {
		return this.weight - o.weight;
	}
}
